import java.lang.reflect.Array;
import java.util.Arrays;

public class Main1 {
    public static void main(String[] args) {
        int[] arr = new int[] {1,2,4,7,4,2,3};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void quickSort(int[] arr) {
        quick(arr,0,arr.length-1);
    }
    //对基准值左边快排，右边快排
    private static void quick(int[] arr,int l,int r) {
        if(l >= r) {
            return;
        }

        int piv = partition(arr,l,r);
        quick(arr,l,piv-1);
        quick(arr,piv+1,r);
    }

    //分区：小的放左边，大的放右边
    private static int partition(int[] arr,int l,int r) {
        int tmp = arr[l];
        int t = l;

        while(l < r) {
            //找到右边小的
            while(l < r && arr[r] >= tmp) {
                r--;
            }
            while (l < r && arr[l] <= tmp) {
                l++;
            }
            swap(arr,l,r);
        }
        swap(arr,t,l);
        return l;
    }

    private static void swap(int[] arr,int l,int r) {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
    }
}
